package com.base.dataStructure.recurrence;

import java.util.Arrays;

/**
 * @Author: hdhao
 * @Create: 2023/3/28 - 20:48
 * @Version: v1.0
 */
//使用递归完成冒泡排序
public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {3,6,2,1,8};
        System.out.println(Arrays.toString(a));
//        bubble1(a,a.length-1);
//        System.out.println(Arrays.toString(a));

        bubble(a);
        System.out.println(Arrays.toString(a));

    }

    /**
     * 双重for循环实现冒泡排序
     * @param a
     */
    private static void bubble(int[] a){
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length-1-i; j++) {
                int temp;
                if (a[j] > a[j+1]){
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }
    /**
     * 递归实现冒泡排序
     * @param a
     * @param end 代表未排序区域的右边界
     */
    private static void bubble1(int[] a,int end){
        if (end == 0){
            return;
        }
        for (int i = 0; i < end; i++) {
            if (a[i] > a[i+1]){
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
        bubble1(a,end-1);
    }

    /**
     * 优化递归冒泡排序
     * @param a
     * @param end
     */
    private static void bubble2(int[] a,int end){
        if (end == 0){
            return;
        }
        int x = 0;
        for (int i = 0; i < end; i++) {
            if (a[i] > a[i+1]){
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                x = i;
            }
        }
        bubble2(a,x);
    }
}
